#include <iostream>
#include <vector>
struct TreeNode {
      int val;
      TreeNode *left;
      TreeNode *right;
      TreeNode() : val(0), left(nullptr), right(nullptr) {}
      TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
      TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 };
using namespace std;
// 1.确定当前根节点：
// 从前序遍历序列中，通过当前索引peri（引用传递，
// 用于跟踪前序序列的处理位置）获取当前子树的根节点值，创建根节点。

// 2.划分左右子树范围：在中序遍历序列中，查找根节点值对应的位置rooti。这个位置将中序序列分为：
// 左子树范围：[instart, rooti-1]（根节点左侧的所有元素构成左子树的中序序列）；
// 右子树范围：[rooti+1, inend]（根节点右侧的所有元素构成右子树的中序序列）。

// 3.递归构建左子树：若左子树范围有效（instart <= rooti-1），
// 则递增peri（前序序列的下一个元素是左子树的根），递归调用函数构建左子树，
// 并将结果赋值给当前根节点的left指针；否则左子树为nullptr。

// 4.递归构建右子树：若右子树范围有效（rooti+1 <= inend），
// 则再次递增peri（前序序列中左子树之后的元素是右子树的根），递归调用函数构建右子树，
// 并将结果赋值给当前根节点的right指针；否则右子树为nullptr。

class Solution {
public:
    TreeNode* _buildTree(vector<int>& preorder, vector<int>& inorder,int& peri,int instart,int inend)
    {
        //先序确定根
        //中序确定左右子树
        TreeNode* root = new TreeNode(preorder[peri]); //构造根节点 
        //找出根节点在中序遍历的位置来确定根的左右子树有那些
        int rooti=0;
        while(rooti<=inend)
        {
            if(inorder[rooti] == preorder[peri])
            {
                break;
            }
            else
            {
                rooti++;
            }
                
        }

        //处理左右子树如果根的左边还有数就递归构建左树
        if(instart <= rooti-1)
        {
           root->left = _buildTree(preorder,inorder,++peri,instart,rooti-1);
        } 
        else
        {
            root->left = nullptr;
        }
        //如果根的右边有数就递归构建右树        
        if(rooti+1 <= inend)
        {
            root->right = _buildTree(preorder,inorder,++peri,rooti+1,inend);
        }
        else
        {
            root->right = nullptr;
        }
        return root;
        
    }
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        int peri=0;
        int instart = 0;
        int inend = inorder.size()-1;
        TreeNode* head =   _buildTree(preorder,inorder,peri,instart,inend);
        return head;
    }
};